Solving 10385 - Duathlon (Ternary search)
[andmenj-acm.git] / 10801 - Lift hopping / 10801.cpp
blob05f1d4a541359e5ff37256083a77bad843e8e432
1 #include <sstream>
2 #include <queue>
3 #include <iostream>
4 #include <vector>
6 using namespace std;
8 struct edge{
9 int to, weight, lift;
10 edge(int t, int w, int l) : to(t), weight(w), lift(l) {}
11 bool operator < (const edge &that) const{
12 return weight > that.weight;
16 int main(){
17 int n, k;
18 while (cin >> n >> k){
19 vector<edge> g[100];
20 int t[n];
21 for (int i=0; i<n; ++i){
22 cin >> t[i];
24 string line;
25 getline(cin, line);
26 for (int i=0; i<n; ++i){
27 getline(cin, line);
28 stringstream ss(line);
29 int x, y;
30 ss >> x;
31 while (ss >> y){
32 g[x].push_back(edge(y, (y-x)*t[i], i));
33 g[y].push_back(edge(x, (y-x)*t[i], i));
34 x = y;
38 int d[100][n];
39 for (int i=0; i<100; ++i) for (int j=0; j<n; ++j) d[i][j] = INT_MAX;
40 for (int j=0; j<n; ++j) d[0][j] = 0;
42 priority_queue<edge> q;
43 q.push(edge(0, -60, -1));
44 while (q.size()){
45 edge top = q.top(); q.pop();
47 if (top.to == k) break;
48 if (d[top.to][top.lift] < top.weight) continue;
50 for (int i=0; i<g[top.to].size(); ++i){
51 edge u = g[top.to][i];
53 int t;
54 if ((t = top.weight + u.weight + (top.lift != u.lift?60:0)) < d[u.to][u.lift]){
55 d[u.to][u.lift] = t;
56 q.push(edge(u.to, t, u.lift));
60 int a = *min_element(d[k], d[k]+n);
61 if (a < INT_MAX)
62 cout << a << endl;
63 else
64 cout << "IMPOSSIBLE" << endl;
68 return 0;